package algorithm.leetcode.simple;

/*
 编写一个函数来查找字符串数组中的最长公共前缀
 如果不存在公共前缀，返回空字符串 ""。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/8/20
 */
public class Question14 {
    public static void main(String[] args) {
        Question14 question = new Question14();
        String prefix = question.longestCommonPrefix(new String[]{"aca", "cba"});
        System.out.println(prefix);
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String first = strs[0];
        for (int i = 1; i < strs.length; i++) {
            first = longestCommonPrefix(first, strs[i]);
            if (first.length() == 0){
                break;
            }
        }
        return first;
    }

    private String longestCommonPrefix(String str1, String str2) {
        int minLen = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < minLen && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}
